package tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class averageOfLevels {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();
        if (root == null){
            return result;
        }
        que.offerLast(root);
        while (!que.isEmpty()){
            int leveSize = que.size();
            double sum = 0.0;
            for (int i = 0; i < leveSize; i++) {
                TreeNode poll = que.pollFirst();
                if (poll.left != null){
                    que.offerLast(poll.left);
                }
                if (poll.right != null){
                    que.offerLast(poll.right);
                }
                sum += poll.val;
                if (i == leveSize -1){
                    result.add(sum/leveSize);
                }
            }
        }
        return result;
    }
}
